//1.二分法查找
let list = [1, 8, 3, 5, 6, 4, 7, 2,9]
function search(list, item) {
    let min = 0 //最小下标
    let max = list.length - 1;//最大下标
    list.sort((a,b)=>{
        return a-b
    })
    while (min < max) {
        let mid = Math.floor((min+max)/2)
        if(item==list[mid]){
            return mid
        }else if(item>list[mid]){
            min=mid+1
        }else{
            max = mid-1
        }
    }
    return max
}
console.log(search(list,7));
//2.冒泡排序
function swap(array, a, b) {//交换
    [array[a], array[b]] = [array[b], array[a]]
}
let num = 0;
let sum = 0;
//(1)
function bubble(array) {
    const { length } = array
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1; j++) {
            sum = num + 1
            num++
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]]
            }
        }
    }
    return array
}
//(2)
function Bubble(array) {
    const { length } = array
    for (let i = 0; i < length - 1; i++) {
        for (let j = 0; j < length - 1 - i; j++) {
            sum = num + 1
            num++
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]]
            }
        }
    }
    return array
}
let arr = bubble([2, 6, 4, 1, 0, 8])
console.log(arr);
// 3.插入排序
function insertSort(arr){
    const {length}=arr;
    for(let i = 1; i<length;i++){
        let j = i;
        temp = arr[i];
        while(j>0&&arr[j-1]>temp){
            arr[j]=arr[j-1]
            j--
        }
        arr[j]=temp
    }
    return arr
}
console.log(insertSort(arr));
//4.选择排序
function selectSort(arr){
    let {length} = arr
    for(let i =0;i<length-1;i++){
        let indexMin = i;
        for(let j = i+1;j<length;j++){
            if(arr[indexMin]>arr[j]){
                indexMin=j
            }
        }
        if(i!=indexMin){
            [arr[i],arr[indexMin]]=[arr[indexMin],arr[i]]
        }
    }
    return arr
}
console.log(selectSort(arr));
//5.快速排序
function quickSort(arr ){
    if(arr.length <= 1){
        return arr
    }
    let pro = arr[0];
    let left = [];
    let right = [];
    for(let i=1;i<arr.length;i++){
        if(arr[i]<=pro){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    let l = quickSort(left);
    let r = quickSort(right);
    return l.concat(pro).concat(r)
}